package 中等;

import java.math.BigDecimal;

public class 最长回文子串5 {

    public static void main(String[] args) {
        String s = "aaaaa";
        最长回文子串5 t = new 最长回文子串5();
        System.out.println(t.longestPalindrome1(s));
    }

    //中心扩散解法
    public  String longestPalindrome(String s) {
        int begin  = 0;
        int end = 0;
        int oddLength;
        int evenLength;
        int maxLength;
        for (int i = 0; i < s.length()-1; i++) {
            oddLength = expandAroundCenter(s,i ,i );
            evenLength = expandAroundCenter(s,i ,i+1 );
            maxLength = Math.max(oddLength,evenLength );
            if (maxLength>end-begin){
                    begin = i - (maxLength-1)/2;
                    end = i + maxLength/2;
            }
        }
        return s.substring(begin,end +1);

    }

    public int expandAroundCenter(String s,int left,int right){
        int length;

        if (left==right){
            length=1;
        }else {
            if (s.charAt(left)!=s.charAt(right)){
                return 0;
            }
            length =2;
        }
        while (left-1>=0 && right+1<s.length()){
            if (s.charAt(left-1)==s.charAt(right+1)){
                length +=2;
                left--;
                right++;
            }else {
                return length;
            }
        }
        return length;
    }




    /**
     * 对于一个子串而言,如果它是回文串,并且长度大于2,那么将它首尾的两个字母去除之后,它仍然是个回文串。
     * 例如对于字符串"ababa",如果我们已经知道"bab"是回文串,那么"ababa"一定是回文串,这是因为它的首尾两个字母都是"a"根据这样的思路,
     * 我们就可以用动态规划的方法解决本题。我们用P(i,j)表示字符串s的第i到j个字母组成的串(下文表示成s[i :j])是否为回文串
     *P(i,j) {
     *true, 如果子串Si ..Ss是回文串
     * false, 其他情况
     * }
     * 这里的「其它情况」包含两种可能性:
     * 1. s[i :j]本身不是一个回文串;
     * 2·i>j,此时s[i :j]本身不合法。
     * 那么我们就可以写出动态规划的状态转移方程:P(i,j)=P(i+1,j-1)&&(Si==Sj)也就是说,只有s[i+1 :j-1]是回文串,
     * 并且s的第i和j个字母相同时, s[i :j]才会是回文串。
     * 上文的所有讨论是建立在子串长度大于2的前提之上的,我们还需要考虑动态规划中的边界条件,即子串的长度为1或2。
     * 对于长度为1的子串,它显然是个回文串;对于长度为2的子串,只要它的两个字母相同它就是一个回文串。
     * 因此我们就可以写出动态规划的边界条件:
     * {
     *     P(i,i) = true
     *     P(i,i+1) =(Si==Si+1)
     * }
     * 根据这个思路,我们就可以完成动态规划了,最终的答案即为所有P(i,j)=true 中j-i+1 (即子串长·度)的最大值。
     * 注意:在状态转移方程中,我们是从长度较短的字符串向长度较长的字符串进行转移的,因此一定要注意动态规划的循环顺序。
     * @param s
     * @return
     */
    public  String longestPalindrome1(String s) {
        int length = s.length();
        if (length<2){
            return s;
        }
        boolean[][] isPalindrome = new boolean[length][length];//
        String result = "";
        for (int j = 1; j < length; j++) {
            for (int i = 0; i <= j; i++) {
                if (i==j){
                    isPalindrome[i][j] = true;
                }
                if (s.charAt(i)!=s.charAt(j)){
                    isPalindrome[i][j] = false;
                }else {
                    if (j-i<3){
                        isPalindrome[i][j] = true;
                    }else {
                        isPalindrome[i][j] = isPalindrome[i+1][j-1];
                    }
                }
                if (isPalindrome[i][j]&&j-i+1>result.length()){
                    result = s.substring(i,j+1 );
                }
            }

        }

        return result;
    }
}
